Multi-processor computing systems are becoming increasingly more common in a variety of applications. A multi-processor system is one that includes multiple processors, where the processors can be physical processors, processors with multiple cores, logical processors, or any combination thereof. A single physical processor can implement multiple logical processors, as illustrated in FIG. 1, in which one physical processor 6 includes two logical processors 7. In such an implementation, the logical processors generally have some private state, but a portion of the state is shared. The shared state is known as the global state. Accordingly, the global state is a state that is shared by a plurality of processes and/or threads running in a multi-processor environment. Henceforth in this document, the term “processor” is intended to mean either a physical processor or a logical processor unless the term is otherwise qualified.
In a multi-processor environment, as illustrated in FIG. 2, multiple processes or threads 10 and 11 can execute at the same time, i.e., in parallel, and can work on a large amount of global or shared data 12. A file server typically performs two functions that update global state or counters, such as metadata. The first function is to process client operations including making changes to the global state in memory at block 13, and the second is to flush the file system changes to disk 14 upon having resolved any conflicts or inconsistencies.
Updating the global state in a parallel fashion is desirable, but cannot always be performed due to the potential for inconsistency or conflict. Parallelizing updates allows multiple units of work to happen in one unit of time. For instance, for two tasks, A, and B, that take “T” amount of time each, performing them in sequence requires 2T time, while performing them in parallel requires only T time.
One solution has been to use mutual exclusion, where both processes (client-handling and storage-handling) take a lock. A lock is a mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. A lock is thus, one way of enforcing concurrency control policies. Most locking designs block the execution of the process requesting the lock until it is allowed to access the locked resource. Locks can be efficient if the execution of the process is only likely to be blocked for a short period of time, as it avoids the overhead of operating system process re-scheduling. However, locks are wasteful if the lock is held for a long period of time. In this case, locks lead to a lot of contention, which is measured by the amount of work that cannot be done during the wait.
One solution to the problem of parallelizing updates to global state is to determine all global state updates, and take individual locks for each global counter that is to be updated. However, more locks means more complexity, more code updating, more bugs, also creates overhead of process scheduling (figuring out which process takes which lock, etc.)